Matematica Discreta: I Fondamenti del Conteggio

Il contare è l'arte di determinare la dimensione di insiemi finiti senza il noioso lavoro dell'enumerazione fisica. Sfruttando strutture logiche, possiamo risolvere problemi che vanno dalle semplici combinazioni di menu alle complesse permutazioni crittografiche.

La Logica di "O" e "E"

Due pilastri sostengono l'intero campo della combinatoria. Il loro utilizzo dipende interamente dal fatto che consideriamo un compito come una scelta singola tra diverse categorie o come una sequenza di scelte.

Il Principio dell'Addizione (Regola della Somma)

Se un insieme $X$ è suddiviso in sottoinsiemi disgiunti $X_1, X_2, \dots, X_n$, allora il numero totale di elementi $|X|$ è la somma delle dimensioni di quei sottoinsiemi:

$$|X| = |X_1| + |X_2| + \dots + |X_n|$$

Analogia: Scegliere un pasto al Kay’s Quick Lunch scegliendo un panino dal menù dei Piatti Principali O un antipasto dal menù degli Antipasti. Non puoi avere entrambi; scegli un solo piatto.

Il Principio della Moltiplicazione (Regola del Prodotto)

Se un'attività consiste in $t$ passaggi successivi, dove il passaggio $i$ ha $n_i$ esiti possibili, il numero totale di modi per completare il compito è il prodotto delle possibilità a ciascun passaggio:

$$N = n_1 \times n_2 \times \dots \times n_t$$

Analogia: Configurare un camion "Big Pickup". Devi scegliere un motore (5 opzioni) E uno stile di cabina (3 opzioni). Il numero totale di configurazioni è pari a $5 \times 3 = 15$.

Implementazione in Codice e Complessità

In informatica, questi principi si manifestano nelle strutture di ciclo. Cicli sequenziali rappresentano il Principio dell'Addizione, mentre cicli annidati rappresentano il Principio della Moltiplicazione.

// Principio dell'Addizione (esecuzioni: m + n)

per i da 1 a m: stampa(i)

per j da 1 a n: stampa(j)

// Principio della Moltiplicazione (esecuzioni: m * n)

per i da 1 a m:

per j da 1 a n:

stampa(i, j)

🎯 Principio Fondamentale

Distingui per parole chiave: "O" indica Addizione (scelte mutuamente esclusive), mentre "E" o "Successivo" indica Moltiplicazione (passaggi indipendenti in una sequenza).

DOMANDA 1

Quanti pasti al Kay's Quick Lunch (Figura 6.1.1) sono composti da un antipasto e una bevanda, supponendo che ci siano 3 antipasti e 4 bevande?

DOMANDA 2

Nello snippet di codice fornito, quante volte vengono eseguite le istruzioni di stampa in totale? [Codice: per i da 1 a m, stampa(i), per j da 1 a n, stampa(j)]

m × n

$m + n$

$m^n$

$n^m$

DOMANDA 3

Quante stringhe di lunghezza 3 possono essere formate usando le lettere {A, B, C, D, E} se si permettono ripetizioni?

125

243

DOMANDA 4

Usando la chiave pubblica (n=713, e=29), qual è l'encrypt della messaggio M = 333?

333

557

128

712

DOMANDA 5

Quante stringhe di lunghezza 3 usando le lettere {A, B, C, D, E} contengono almeno una volta la lettera A (ripetizioni consentite)?

125

Sfida: Ragionamento Combinatorio Avanzato

Camion, Triangoli e Caselle per Piccioni

Scenario: I grandi pick-up sono apprezzati per le apparentemente infinite modalità di personalizzazione. Un articolo del New York Times suggerisce che servono abilità matematiche di Will Hunting per contare le configurazioni. Analizziamo un modello con 5 opzioni di motore (3.9L V6, 5.2L V8, 5.9L V8, 5.9L Diesel turbo, 8L V10).

Definisci ordine lessicografico e spiega perché è utile nelle strutture di conteggio.

Soluzione: L'ordine lessicografico è una generalizzazione dell'ordine alfabetico delle parole in un dizionario a sequenze di simboli ordinati. Date due sequenze $a_1...a_n$ e $b_1...b_n$, diciamo che $a < b$ se nell'indice $i$ più piccolo dove $a_i \neq b_i$, abbiamo $a_i < b_i$. È utile perché fornisce un modo sistematico per elencare tutte le permutazioni o combinazioni senza omissioni o ripetizioni.

Che cos'è una permutazione di $x_1, \dots, x_n$? Fornisci una definizione formale.

Soluzione: Una permutazione di un insieme di oggetti distinti è un ordinamento di tali oggetti. Per un insieme di $n$ elementi, una permutazione è una bigezione dall'insieme $\{1, 2, \dots, n\}$ a sé stesso, dove l'ordine degli elementi nella sequenza risultante conta.

Dimostra che se cinque carte sono estratte da un mazzo standard da 52 carte, almeno due carte hanno lo stesso seme.

Soluzione: Questo è un'applicazione del Principio dei Piccioni. Ci sono 4 semi possibili (le "caselle") e vengono scelte 5 carte (i "piccioni"). Poiché $5 > 4$, per il Principio dei Piccioni, almeno un seme deve contenere $\lceil 5/4 \rceil = 2$ carte. Pertanto, almeno due carte devono condividere un seme.

In quanti modi possiamo selezionare otto palline da un sacchetto contenente palline rosse, blu e gialle (almeno 8 di ciascuna)? (Difficoltà: Parole chiave: 18, Lunghezza: Breve)

Soluzione: Questo è un problema di combinazioni con ripetizione. Usando la formula delle stelle e barre $C(n+r-1, r)$ con $n=3$ categorie e $r=8$ selezioni: $C(3+8-1, 8) = C(10, 8) = C(10, 2) = (10 \times 9) / 2 = 45$ modi.